An official website of the United States government
An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $$G$$ and $$H$$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $$G$$ or a blue $$H$$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $$r_o(G,H)$$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $$r_o(G,P_n)$$ for fixed $$G$$, where $$P_n$$ is the monotone ordered path. We prove an $$O(n \log n)$$ bound on $$r_o(G,P_n)$$ for all $$G$$ and an $O(n)$ bound when $$G$$ is $$3$$-ichromatic; we partially classify graphs $$G$$ with $$r_o(G,P_n) = n + O(1)$$. Many of these results extend to $$r_o(G,C_n)$$, where $$C_n$$ is an ordered cycle obtained from $$P_n$$ by adding one edge.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
null (Ed.)Abstract The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a K r+ 1 -free graph on n vertices with e ( G ) > ex( n , K r +1 )– α n 2 , then one can remove εn 2 edges from G to obtain an r -partite graph. Füredi gave a short proof that one can choose α = ε . We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.more » « less
-
A hypergraph $$\mathcal H$$ is super-pancyclic if for each $$A \subseteq V(\mathcal H)$$ with $$|A| \geqslant 3$$, $$\mathcal H$$ contains a Berge cycle with base vertex set $$A$$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient. In particular, they are sufficient for every hypergraph $$\mathcal H$$ with $$ \delta(\mathcal H)\geqslant \max\{|V(\mathcal H)|, \frac{|E(\mathcal H)|+10}{4}\}$$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $$G$$ such that for each $$A \subseteq X$$ with $$|A| \geqslant 3$$, $$G$$ has a cycle $$C_A$$ such that $$V(C_A)\cap X=A$$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.more » « less
